package com.lw.leetcode.sort.b;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA.
 * sort
 * 1631. 最小体力消耗路径
 *
 * @author liw
 * @version 1.0
 * @date 2021/12/6 12:14
 */
public class MinimumEffortPath {

    public static void main(String[] args) {
        MinimumEffortPath test = new MinimumEffortPath();
        PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> Integer.compare(a, b));
        queue.add(1);
        queue.add(4);
        queue.add(3);
        queue.add(6);

        System.out.println(queue.poll());
        System.out.println(queue.poll());
        System.out.println(queue.poll());
    }


    private PriorityQueue<Node> queue = new PriorityQueue<>((a, b) -> Integer.compare(a.value, b.value));
    private int[][] arr;
    private int[][] heights;
    public int minimumEffortPath(int[][] heights) {
        int a = heights.length - 1;
        int b = heights[0].length - 1;
        queue.add(new Node(0, 0, 0));
        arr = new int[a + 1][b + 1];
        this.heights = heights;
        for (int[] ints : arr) {
            Arrays.fill(ints, -1);
        }
        arr[0][0] = 0;
        while (!queue.isEmpty()) {
            Node poll = queue.poll();
            int value = poll.value;
            int x = poll.x;
            int y = poll.y;
            if (arr[x][y] != value) {
                continue;
            }
            int r = arr[a][b];
            if (r != -1 && value >= r) {
                return r;
            }
            int v = heights[x][y];
            if (x > 0) {
                find(v, value, x - 1, y);
            }
            if (x < a) {
                find(v, value, x + 1, y);
            }
            if (y > 0) {
                find(v, value, x, y - 1);
            }
            if (y < b) {
                find(v, value, x, y + 1);
            }
        }
        return arr[a][b];
    }

    private void find(int v, int value, int x, int y) {
        int item = arr[x][y];
        int max = Math.max(Math.abs(v - heights[x][y]), value);
        if (item == -1 || item > max) {
            queue.add(new Node(max, x, y));
            arr[x][y] = max;
        }
    }

    class Node {
        int value;
        int x;
        int y;
        public Node(int value, int x, int y) {
            this.value = value;
            this.x = x;
            this.y = y;
        }
    }
}
